第4题
阅读下列说明和C代码，回答问题1至问题3，将解答写在答题纸的对应栏内。
【说明】
模式匹配是指给定主串t和子串s，在主串t中寻找子串s的过程，其中s称为模式。如果匹配成功，返回s在t中的位置，否则返回-1。
KMP算法用next数组对匹配过程进行了优化。KMP算法的伪代码描述如下：
1．在串t和串s中，分别设比较的起始下标i=j=0。
2．如果串t和串s都还有字符，则循环执行下列操作：
(1) 如果j=-1或者t[i]=s[j]，则将i和j分别加1，继续比较t和s的下一个字符；
(2) 否则，将j向右滑动到next[j]的位置，即j=next[j]。
3．如果s中所有字符均已比较完毕，则返回匹配的起始位置(从1开始)；否则返回-1．
其中，next数组根据子串s求解。求解next数组的代码已由get_next函数给出。
【C代码】
(1) 常量和变量说明
(2) C程序
【说明】
模式匹配是指给定主串t和子串s，在主串t中寻找子串s的过程，其中s称为模式。如果匹配成功，返回s在t中的位置，否则返回-1。
KMP算法用next数组对匹配过程进行了优化。KMP算法的伪代码描述如下：
1．在串t和串s中，分别设比较的起始下标i=j=0。
2．如果串t和串s都还有字符，则循环执行下列操作：
(1) 如果j=-1或者t[i]=s[j]，则将i和j分别加1，继续比较t和s的下一个字符；
(2) 否则，将j向右滑动到next[j]的位置，即j=next[j]。
3．如果s中所有字符均已比较完毕，则返回匹配的起始位置(从1开始)；否则返回-1．
其中，next数组根据子串s求解。求解next数组的代码已由get_next函数给出。
【C代码】
(1) 常量和变量说明
(2) C程序
【问题：4.1】根据题干说明，填充C代码中的空(1)～(4).
【问题：4.2】根据题干说明和C代码，分析出kmp算法的时间复杂度为(5)(主串和子串的长度分别为lt和ls，用O符号表示)。
【问题：4.3】根据C代码，字符串“BBABBCAC”的next数组元素值为(6)(直接写素值，之间用逗号隔开)。若主串为“AABBCBBABBCACCD”，子串为“BBABBCAC”，则函数Kmp的返回值是(7)。